/**
 * 260. 只出现一次的数字 III
 */
class Solution9 {
    public int[] singleNumber(int[] nums) {
        int xoy = 0;
        for(int num : nums) {
            xoy ^= num;
        }

        // 提取xoy最右边的1
        int lowbit = xoy & (-xoy);
        int x = 0, y = 0;
        int[] ret = new int[2];
        // 根据lowbit可以把数组分为两组：一组是lowbit位置是0，一组是lowbit位置不是0
        for(int num : nums) {
            if((lowbit & num) != 0) {
                x ^= num;
            } else {
                // (lowbit & num) == 0
                y ^= num;
            }
        }
        ret[0] = x; ret[1] = y;

        return ret;
    }
}